In various applications there is a need for a run-time support system to monitor which objects are modified by concurrently running mutators. Typically the run-time support system (such as a Java virtual machine) implements certain functionality, such as garbage collection or distributed shared memory, concurrently with mutator execution.
F. Pizlo et al: A study of Concurrent Real-Time Garbage Collectors, PLDI'08, pp. 33-44, ACM, 2008, which is hereby incorporated herein by reference, describes a number of garbage collectors where mutators execute concurrently with the garbage collection.
An important element of concurrent (copying/compacting) garbage collector implementations is copying (relocating) objects while mutators are executing.
US patent application publication 2008/0281886 A1 (Petrank et al), Nov. 13, 2008 “Concurrent, lock-free object copying” describes, among other things, a relocating mechanism that moves an object by using a status field related to a data field, possibly in an interim (wide) object space, which is then copied to a to-space object.
US 2009/0222494 A1 (Pizlo et al), Sep. 3, 2009 “Optimistic object relocation” describes, among other things, a technique wherein memory accesses are monitored for a write to an object [that is being relocated], and if a write is detected during relocation, the relocation fails and the memory at the destination address is deallocated; but if no write is detected, the relocation succeeds and the references are updated to point to the destination address. The aborted relocation may then be retried (to a newly allocated destination address).
US 2009/0222634 A1 (Pizlo et al), Sep. 3, 2009 “Probabilistic object relocation” describes, among other things, a method of relocating objects where the object relocation may mark the words of the object during relocation with a relocation value to indicate transfer to the destination memory without locking the threads. The threads may be configured to check the value in the source memory during object access, and to access the corresponding word of the destination memory if the source memory word comprises the relocation value.
The above patent application publications are hereby incorporated herein by reference.
Various copying mechanisms, such as the “Optimistic object relocation” mechanism referred to above, rely on monitoring objects being copied to detect when an object is written into, and to take some suitable action. The optimistic object relocation method, for example, may use atomic instructions (compare-and-swap) in the write barrier for setting a relocation status semaphore to indicate that copying should be aborted if the object is written into during copying.
However, using atomic instructions incurs a significant overhead on program execution, and therefore it would be desirable to avoid their use.
D. Detlefs et al: Garbage-First Garbage Collection, ISMM'04, p. 37-48, ACM, 2004, which is hereby incorporated herein by reference, describes a garbage collector that uses a card marking write barrier together with log buffers (for recording identities of dirty cards) and a background thread for scanning dirty cards and updating remembered sets.
Distributed shared memory implementations also monitor writes. There, monitoring is often performed at the granularity of a memory page or a cache line, using, e.g., memory protection or special hardware for implementing the monitoring. To implement fine-grained detection of writes, techniques such as computing a “diff” (difference) between an original and the modified page are used.
I. Schoinas: Fine-Grain Distributed Shared Memory on Clusters of Workstations, PhD Thesis, University of Wisconsin-Madison, 1998, which is hereby incorporated herein by reference, surveys various distributed shared memory systems, particularly those supporting fine-grained updates and presents its own solutions for such updates.
K. Kavi et al: Shared Memory and Distributed Shared Memory Systems: A Survey, Advances in Computers, vol. 53, pp. 55-108, Academic Press, 2000, which is hereby incorporated herein by reference, presents a survey of distributed shared memory implementations.
A. Moga and M. Dubois: A comparative evaluation of hybrid distributed shared-memory systems, Journal of Systems Architecture, 55:43-52, 2009, which is hereby incorporated herein by reference, presents a recent comparison of various systems for implementing distributed shared memory using the combination of software and special hardware for node-local operations.
It should be noted that the term write barrier is used in this disclosure in its garbage collection sense (roughly, a section of code or logic that intercepts writes and performs some bookkeeping actions in connection with a write), as opposed to its meaning in memory systems and processor architecture relating to memory ordering.
It would be desirable to monitor writes in distributed shared memory implementations more efficiently than is possible with the current methods for general-purpose computers. More efficient write monitoring would also benefit real-time garbage collectors, Java virtual machines, very large garbage collected systems (such as semantic search systems and knowledge processing systems), and generally future cluster computing systems where several nodes execute the same application.